A graph (G) is typically a structure consisting of a set of vertices (V) and a set of edges (E) used to represent relationships between the vertices. For instance, a participation graph can be used to relate entities one to another based upon common conditions, properties, parameters, characteristics, activities, connections, and so forth. Such graphs may be employed for analysis of corresponding data sets in many scenarios. An example of such a scenario is in the context of online ad auctions for ad space that is associated with resources from a service provider. In the ad auction context, an auction participation graph is a structure that contains vertices representing advertisers who compete in the auctions and edges that connect two vertices when advertisers represented by the vertices are related by participating in auctions together. The auction participation graph contains a wealth of information that has many applications including advertiser flighting, suggestion of keywords to advertisers, micro-market analysis, and so forth.
Often, analysis of a graph of this type involves finding meaningful subsets or clusters within the graph. For the example auction participation graph, this may correspond to clustering the graph to identify submarkets in the advertiser graph that have relatively low interaction one to another. More generally, clustering may involve identifying clusters to optimize some objective function. Clustering a graph, though, can become quite difficult as the graph becomes larger (more vertices) and more dense (more edges between the vertices) due to the number of computations involved in the clustering. Thus, traditional algorithms used to directly cluster graphs may be unable to successfully perform clustering for larger and denser graphs that arise in some scenarios.